//
// Description: 2267. 检查是否有合法括号字符串路径
// Created by Loading on 2022/5/16.
//

#include <bits/stdc++.h>

using namespace std;

bool hasValidPath(vector<vector<char>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    // 路径长度必须是偶数，且第一个位置和最后一个位置必须是 "()"
    if ((m + n - 1) % 2 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
        return false;
    }

    vector<vector<vector<bool>>> visit(m, vector<vector<bool>>(n, vector<bool>(m + n)));
    function<bool(int, int, int)> dfs = [&](int x, int y, int k) {
        // 左括号数量过多。即使剩余路径全是右括号也不合法
        if (k > m - x + n - y + 1) {
            return false;
        }
        // 到达终点，终点前的状态需要 k = 1
        if (x == m - 1 && y == n - 1) {
            return k == 1;
        }
        // 重复寻找
        if (visit[x][y][k]) {
            return false;
        }
        visit[x][y][k] = true;
        k += grid[x][y] == '(' ? 1 : -1;
        // k 需全状态 >= 0，向右或向下寻找
        return k >= 0 && ((x + 1 < m && dfs(x + 1, y, k)) || (y + 1 < n && dfs(x, y + 1, k)));
    };

    return dfs(0, 0, 0);
}

int main() {
    vector<vector<char>> grid = {{'(', '(', '('},
                                 {')', '(', ')'},
                                 {'(', '(', ')'},
                                 {'(', '(', ')'}};
    bool res = hasValidPath(grid);
    cout << res << endl;

    return 0;
}